Міністерство освіти і науки України Національний університет «Львівська політехніка» Кафедра ЕОМ Лабораторна робота №3 «Алгоритм електронного цифрового підпису RSA» Виконав: студент групи СКС-5 Львів-2006 1.Мета: засвоїти алгоритм електронного цифрового підпису RSA. 2.Теоретична частина: Технологія застосування системи електронного цифрового підпису (ЕЦП) враховує наявність мережі абонентів, що посилають оди одному підписані цифрові документи. Для кожного абонента генерується пара ключів: секретний та відкритий. Секретний ключ зберігається абонентом у таємниці і використовується їм для формування ЕЦП. Відкритий ключ відомий усім іншим користувачам і призначений для перевірки ЕЦП одержувачем підписаного електронного документа. В алгоритмах ЕЦП, як і в асиметричних системах шифрування, використовується різні математичні схеми, засновані на застосуванні одно направлених функцій. Ці схеми розділяються на дві групи. В основі такого поділу лежать відомі складні обчислювальні задачі: задача факторизації (розкладання на множники) великих цілих чисел; задача дискретного логарифмування; Першою і найбільш відомою у всьому світі конкретною системою ЕЦП стала система RSA, математична схема якого була розроблена у 1977 році в Массачусетскому технологічному інституті США. Спочатку необхідно обчислити пару ключів (секретний та відкритий). Для цього відправник (автор) електронних документів обчислює два великих простих числа P та Q, потім знаходить їх добуток  EMBED Equation.3 
 і значення функції  EMBED Equation.3 
. Далі відправник обчислює число Е з умов:  EMBED Equation.3 
 та число D з умов:  EMBED Equation.3 
 Пара чисел (E,N) є відкритим ключем, який автор передає партнерам по переписці для перевірки його цифрових підписів. Число D зберігається автором як секретний ключ для підпису. Узагальнена схема формування і перевірки цифрового підпису RSA показана на рис.1.
Рис.1. Узагальнена схема система цифрового підпису RSA Припустимо, що відправник хоче підписати повідомлення Ь перед його відправкою. Спочатку повідомлення М (блок інформації, файл, таблиця) стискаються з допомогою хеш-функції h(∙) у ціле число m: m=h(M). Потім обчислюють цифровий підпис S під електронним документом М, використовуючи хеш-значення m і секретний ключ D:  EMBED Equation.3 
. Пара (M,S) передається партнеру-одержувачу як електронний документ М, підписаний цифровим підписом S, причому підпис S сформований власником секретного ключа D. Після приймання пари (M,S) отримувач обчислює хеш-значення повідомлення М двома різними способами. Насамперед він відновлює хеш-значення m’,застосовуючи криптографічне перетворення підпису S з використанням відкритого ключа Е:  EMBED Equation.3 
. Крім того, він знаходить результат хешування прийнятого повідомлення М з допомогою токої ж хеш-функції h(∙): m=h(M). Якщо спостерігається рівність обчислених значень, тобто  EMBED Equation.3 
 одержувач признає пару (M,S) дійсною. Доведено, що тільки власник секретного ключа D може сформувати цифровий підпис S по документу M, а визначити секретне число D по відкритому числу E не легше, н...